package NewCoder;

public class BM76 {
    public boolean match (String str, String pattern) {
        //   write code here
        int len1=str.length();
        int len2=pattern.length();
        boolean[][] dp=new boolean[len1+1][len2+1];
        dp[0][0]=true;
        for(int i=2;i<=len2;i+=2){
            if(pattern.charAt(i-1)=='*'){
                dp[0][i]=dp[0][i-2];
            }
        }

        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str.charAt(i-1)==pattern.charAt(j-1) || pattern.charAt(j-1)=='.'){
                    dp[i][j]=dp[i-1][j-1];
                }else if(pattern.charAt(j-1)=='*'){
                    if(dp[i][j-2]){
                        dp[i][j]=true;
                    }else if(str.charAt(i-1)==pattern.charAt(j-2) || pattern.charAt(j-2)=='.'){
                        dp[i][j]=dp[i-1][j];
                    }
                }
            }
        }
        return dp[len1][len2];
    }
}
